package com.yanceysong.codetop.s91_s100;

public class S91_Easy_169_多数元素 {
    /**
     * .S91_Easy_169_多数元素
     * .<p>
     * .<a href="https://leetcode.cn/problems/majority-element/">...</a>
     * .<p>
     * .给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
     * .<p>
     * .你可以假设数组是非空的，并且给定的数组总是存在多数元素。
     * .<p>
     * .示例：
     * .<p>
     * .输入：nums = [3,2,3]
     * .输出：3
     * .<p>
     * .输入：nums = [2,2,1,1,1,2,2]
     * .输出：2
     * .<p>
     * .提示：
     * .<p>
     * .n == nums.length
     * .1 <= n <= 5 * .10^4
     * .-10^9 <= nums[i] <= 10^9
     * .<p>
     * .核心标签：数组、哈希表、分治、计数、排序
     * .<p>
     * .使用摩尔投票算法（Boyer-Moore Voting Algorithm）找出多数元素
     * .<p>
     * .算法原理：
     * .- 多数元素的定义：出现次数 > ⌊n/2⌋，即超过数组长度的一半
     * .- 核心思想：不同元素相互抵消，最后剩下的一定是多数元素
     * .- 使用一个候选人（candidate）和计数器（count）
     * .- 当计数器为0时，选择当前元素作为新候选人
     * .- 遇到相同元素计数+1，遇到不同元素计数-1
     * .- 由于多数元素数量 > n/2，即使所有其他元素都与它抵消，它仍会剩余
     * .<p>
     * .关键洞察：
     * .1. 多数元素的数量严格大于其他所有元素数量之和
     * .2. 即使最坏情况下，多数元素与其他元素一一抵消，多数元素仍会剩余
     * .3. 题目保证一定存在多数元素，所以最后的candidate一定是答案
     * .<p>
     * .图解示例：nums = [2,2,1,1,1,2,2]
     * .<p>
     * .初始状态：
     * .candidate = null, count = 0
     * .<p>
     * .第1步：遍历元素2
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .count = 0，选择2作为候选人
     * .candidate = 2, count = 1
     * .<p>
     * .第2步：遍历元素2
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .与候选人相同，count++
     * .candidate = 2, count = 2
     * .<p>
     * .第3步：遍历元素1
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .与候选人不同，count--
     * .candidate = 2, count = 1
     * .<p>
     * .第4步：遍历元素1
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .与候选人不同，count--
     * .candidate = 2, count = 0
     * .<p>
     * .第5步：遍历元素1
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .count = 0，选择1作为新候选人
     * .candidate = 1, count = 1
     * .<p>
     * .第6步：遍历元素2
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .与候选人不同，count--
     * .candidate = 1, count = 0
     * .<p>
     * .第7步：遍历元素2
     * .[2, 2, 1, 1, 1, 2, 2]
     * .↑
     * .count = 0，选择2作为新候选人
     * .candidate = 2, count = 1
     * .<p>
     * .最终结果：candidate = 2（多数元素）
     * .<p>
     * .抵消过程可视化：
     * .元素2出现4次：2 2 2 2
     * .元素1出现3次：1 1 1
     * .<p>
     * .抵消过程：
     * .2 vs 1 → 抵消
     * .2 vs 1 → 抵消
     * .2 vs 1 → 抵消
     * .2 剩余 → 多数元素
     * .<p>
     * .时间复杂度：O(n)，只需要遍历数组一次
     * .空间复杂度：O(1)，只使用了常数个变量
     * .<p>
     * .其他解法对比：
     * .1. 哈希表统计：时间O(n)，空间O(n)
     * .2. 排序：时间O(nlogn)，空间O(1)或O(n)
     * .3. 分治法：时间O(nlogn)，空间O(logn)
     * .4. 摩尔投票：时间O(n)，空间O(1) ← 最优解
     */
    public int majorityElement(int[] nums) {
        // 计数器：记录当前候选人的"优势"
        int voteCount = 0;
        // 候选人：当前认为可能是多数元素的数字
        int candidate = 0;

        // 遍历数组中的每个元素
        for (int currentNum : nums) {
            // 当计数器为0时，说明之前的候选人已被完全抵消
            // 需要选择新的候选人
            if (voteCount == 0) {
                candidate = currentNum;
            }
            
            // 如果当前元素与候选人相同，增加候选人的优势（+1票）
            // 如果当前元素与候选人不同，减少候选人的优势（-1票）
            voteCount += (currentNum == candidate) ? 1 : -1;
        }

        // 由于题目保证一定存在多数元素
        // 最后剩下的候选人一定是多数元素
        return candidate;
    }

    public static void main(String[] args) {
        S91_Easy_169_多数元素 solution = new S91_Easy_169_多数元素();

        System.out.println("=== 多数元素查找测试开始 ===");

        // 测试1: 题目示例1 - [3,2,3]
        System.out.println("\n--- 测试1: [3,2,3] ---");
        testCase1(solution);

        // 测试2: 题目示例2 - [2,2,1,1,1,2,2]
        System.out.println("\n--- 测试2: [2,2,1,1,1,2,2] ---");
        testCase2(solution);

        // 测试3: 单个元素
        System.out.println("\n--- 测试3: 单个元素 [1] ---");
        testSingleElement(solution);

        // 测试4: 两个相同元素
        System.out.println("\n--- 测试4: 两个相同元素 [1,1] ---");
        testTwoSameElements(solution);

        // 测试5: 多数元素在开头
        System.out.println("\n--- 测试5: 多数元素在开头 [5,5,5,1,2] ---");
        testMajorityAtStart(solution);

        // 测试6: 多数元素在末尾
        System.out.println("\n--- 测试6: 多数元素在末尾 [1,2,5,5,5] ---");
        testMajorityAtEnd(solution);

        // 测试7: 多数元素分散分布
        System.out.println("\n--- 测试7: 多数元素分散分布 [1,3,1,3,1,3,1] ---");
        testMajorityScattered(solution);

        // 测试8: 所有元素相同
        System.out.println("\n--- 测试8: 所有元素相同 [7,7,7,7,7] ---");
        testAllSameElements(solution);

        // 测试9: 负数元素
        System.out.println("\n--- 测试9: 负数元素 [-1,-1,-1,2,2] ---");
        testNegativeNumbers(solution);

        // 测试10: 大数组
        System.out.println("\n--- 测试10: 大数组 ---");
        testLargeArray(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试用例1: [3,2,3]
     * .多数元素是3，出现2次 > 3/2 = 1.5
     */
    private static void testCase1(S91_Easy_169_多数元素 solution) {
        int[] nums = {3, 2, 3};
        System.out.println("输入数组: [3, 2, 3]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 3)");
        assert result == 3 : "多数元素应该是3";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试用例2: [2,2,1,1,1,2,2]
     * .多数元素是2，出现4次 > 7/2 = 3.5
     */
    private static void testCase2(S91_Easy_169_多数元素 solution) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("输入数组: [2, 2, 1, 1, 1, 2, 2]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 2)");
        assert result == 2 : "多数元素应该是2";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试用例3: 单个元素 [1]
     * .唯一元素就是多数元素
     */
    private static void testSingleElement(S91_Easy_169_多数元素 solution) {
        int[] nums = {1};
        System.out.println("输入数组: [1]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 1)");
        assert result == 1 : "多数元素应该是1";
        System.out.println("✓ 单个元素测试通过");
    }

    /**
     * .测试用例4: 两个相同元素 [1,1]
     */
    private static void testTwoSameElements(S91_Easy_169_多数元素 solution) {
        int[] nums = {1, 1};
        System.out.println("输入数组: [1, 1]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 1)");
        assert result == 1 : "多数元素应该是1";
        System.out.println("✓ 两个相同元素测试通过");
    }

    /**
     * .测试用例5: 多数元素在开头 [5,5,5,1,2]
     * .多数元素5出现3次 > 5/2 = 2.5
     */
    private static void testMajorityAtStart(S91_Easy_169_多数元素 solution) {
        int[] nums = {5, 5, 5, 1, 2};
        System.out.println("输入数组: [5, 5, 5, 1, 2]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 5)");
        assert result == 5 : "多数元素应该是5";
        System.out.println("✓ 多数元素在开头测试通过");
    }

    /**
     * .测试用例6: 多数元素在末尾 [1,2,5,5,5]
     * .多数元素5出现3次 > 5/2 = 2.5
     */
    private static void testMajorityAtEnd(S91_Easy_169_多数元素 solution) {
        int[] nums = {1, 2, 5, 5, 5};
        System.out.println("输入数组: [1, 2, 5, 5, 5]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 5)");
        assert result == 5 : "多数元素应该是5";
        System.out.println("✓ 多数元素在末尾测试通过");
    }

    /**
     * .测试用例7: 多数元素分散分布 [1,3,1,3,1,3,1]
     * .多数元素1出现4次 > 7/2 = 3.5
     */
    private static void testMajorityScattered(S91_Easy_169_多数元素 solution) {
        int[] nums = {1, 3, 1, 3, 1, 3, 1};
        System.out.println("输入数组: [1, 3, 1, 3, 1, 3, 1]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 1)");
        assert result == 1 : "多数元素应该是1";
        System.out.println("✓ 多数元素分散分布测试通过");
    }

    /**
     * .测试用例8: 所有元素相同 [7,7,7,7,7]
     */
    private static void testAllSameElements(S91_Easy_169_多数元素 solution) {
        int[] nums = {7, 7, 7, 7, 7};
        System.out.println("输入数组: [7, 7, 7, 7, 7]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 7)");
        assert result == 7 : "多数元素应该是7";
        System.out.println("✓ 所有元素相同测试通过");
    }

    /**
     * .测试用例9: 负数元素 [-1,-1,-1,2,2]
     * .多数元素-1出现3次 > 5/2 = 2.5
     */
    private static void testNegativeNumbers(S91_Easy_169_多数元素 solution) {
        int[] nums = {-1, -1, -1, 2, 2};
        System.out.println("输入数组: [-1, -1, -1, 2, 2]");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: -1)");
        assert result == -1 : "多数元素应该是-1";
        System.out.println("✓ 负数元素测试通过");
    }

    /**
     * .测试用例10: 大数组
     * .创建一个包含1000个元素的数组，其中600个是1，400个是2
     */
    private static void testLargeArray(S91_Easy_169_多数元素 solution) {
        int[] nums = new int[1000];
        // 前600个元素为1
        for (int i = 0; i < 600; i++) {
            nums[i] = 1;
        }
        // 后400个元素为2
        for (int i = 600; i < 1000; i++) {
            nums[i] = 2;
        }

        System.out.println("输入数组: [1×600, 2×400] (共1000个元素)");
        int result = solution.majorityElement(nums);
        System.out.println("majorityElement() -> " + result + " (期望: 1)");
        assert result == 1 : "多数元素应该是1";
        System.out.println("✓ 大数组测试通过");
    }
}

